home *** CD-ROM | disk | FTP | other *** search
/ Night Owl 6 / Night Owl's Shareware - PDSI-006 - Night Owl Corp (1990).iso / 039a / jpsrc2.zip / JWRGIF.C < prev    next >
C/C++ Source or Header  |  1991-12-12  |  15KB  |  499 lines
  1. /*
  2.  * jwrgif.c
  3.  *
  4.  * Copyright (C) 1991, Thomas G. Lane.
  5.  * This file is part of the Independent JPEG Group's software.
  6.  * For conditions of distribution and use, see the accompanying README file.
  7.  *
  8.  * This file contains routines to write output images in GIF format.
  9.  *
  10.  * These routines may need modification for non-Unix environments or
  11.  * specialized applications.  As they stand, they assume output to
  12.  * an ordinary stdio stream.
  13.  *
  14.  * These routines are invoked via the methods put_pixel_rows, put_color_map,
  15.  * and output_init/term.
  16.  */
  17.  
  18. /*
  19.  * This code is loosely based on ppmtogif from the PBMPLUS distribution
  20.  * of Feb. 1991.  That file contains the following copyright notice:
  21.  *    Based on GIFENCODE by David Rowley <mgardi@watdscu.waterloo.edu>.
  22.  *    Lempel-Ziv compression based on "compress" by Spencer W. Thomas et al.
  23.  *    Copyright (C) 1989 by Jef Poskanzer.
  24.  *    Permission to use, copy, modify, and distribute this software and its
  25.  *    documentation for any purpose and without fee is hereby granted, provided
  26.  *    that the above copyright notice appear in all copies and that both that
  27.  *    copyright notice and this permission notice appear in supporting
  28.  *    documentation.  This software is provided "as is" without express or
  29.  *    implied warranty.
  30.  *
  31.  * We are also required to state that
  32.  *    "The Graphics Interchange Format(c) is the Copyright property of
  33.  *    CompuServe Incorporated. GIF(sm) is a Service Mark property of
  34.  *    CompuServe Incorporated."
  35.  */
  36.  
  37. #include "jinclude.h"
  38.  
  39. #ifdef GIF_SUPPORTED
  40.  
  41.  
  42. static decompress_info_ptr dcinfo; /* to avoid passing to all functions */
  43.  
  44. #define    MAX_LZW_BITS    12    /* maximum LZW code size (4096 symbols) */
  45.  
  46. typedef INT16 code_int;        /* must hold -1 .. 2**MAX_LZW_BITS */
  47.  
  48. #define LZW_TABLE_SIZE    ((code_int) 1 << MAX_LZW_BITS)
  49.  
  50. #define HSIZE        5003    /* hash table size for 80% occupancy */
  51.  
  52. typedef int hash_int;        /* must hold -2*HSIZE..2*HSIZE */
  53.  
  54. static int n_bits;        /* current number of bits/code */
  55. static code_int maxcode;    /* maximum code, given n_bits */
  56. #define MAXCODE(n_bits)    (((code_int) 1 << (n_bits)) - 1)
  57.  
  58. static int init_bits;        /* initial n_bits ... restored after clear */
  59.  
  60. static code_int ClearCode;    /* clear code (doesn't change) */
  61. static code_int EOFCode;    /* EOF code (ditto) */
  62.  
  63. static code_int free_code;    /* first not-yet-used symbol code */
  64.  
  65. /*
  66.  * The LZW hash table consists of three parallel arrays:
  67.  *   hash_code[i]    code of symbol in slot i, or 0 if empty slot
  68.  *   hash_prefix[i]    symbol's prefix code; undefined if empty slot
  69.  *   hash_suffix[i]    symbol's suffix character; undefined if empty slot
  70.  * where slot values (i) range from 0 to HSIZE-1.
  71.  *
  72.  * Algorithm:  use open addressing double hashing (no chaining) on the
  73.  * prefix code / suffix character combination.  We do a variant of Knuth's
  74.  * algorithm D (vol. 3, sec. 6.4) along with G. Knott's relatively-prime
  75.  * secondary probe.
  76.  *
  77.  * The hash tables are allocated from FAR heap space since they would use up
  78.  * rather a lot of the near data space in a PC.
  79.  */
  80.  
  81. static code_int FAR *hash_code;    /* => hash table of symbol codes */
  82. static code_int FAR *hash_prefix; /* => hash table of prefix symbols */
  83. static UINT8 FAR *hash_suffix;    /* => hash table of suffix bytes */
  84.  
  85.  
  86. /*
  87.  * Routines to package compressed data bytes into GIF data blocks.
  88.  * A data block consists of a count byte (1..255) and that many data bytes.
  89.  */
  90.  
  91. static int bytesinpkt;        /* # of bytes in current packet */
  92. static char packetbuf[256];    /* workspace for accumulating packet */
  93.  
  94.  
  95. LOCAL void
  96. flush_packet (void)
  97. /* flush any accumulated data */
  98. {
  99.   if (bytesinpkt > 0) {        /* never write zero-length packet */
  100.     packetbuf[0] = (char) bytesinpkt++;
  101.     if (FWRITE(dcinfo->output_file, packetbuf, bytesinpkt)
  102.     != (size_t) bytesinpkt)
  103.       ERREXIT(dcinfo->emethods, "Output file write error");
  104.     bytesinpkt = 0;
  105.   }
  106. }
  107.  
  108.  
  109. LOCAL void
  110. char_out (char c)
  111. /* Add a character to current packet; flush to disk if necessary */
  112. {
  113.   packetbuf[++bytesinpkt] = c;
  114.   if (bytesinpkt >= 255)
  115.     flush_packet();
  116. }
  117.  
  118.  
  119. /* Routine to convert variable-width codes into a byte stream */
  120.  
  121. static INT32 cur_accum;        /* holds bits not yet output */
  122. static int cur_bits;        /* # of bits in cur_accum */
  123.  
  124.  
  125. LOCAL void
  126. output (code_int code)
  127. /* Emit a code of n_bits bits */
  128. /* Uses cur_accum and cur_bits to reblock into 8-bit bytes */
  129. {
  130.   if (cur_bits > 0)
  131.     cur_accum |= ((INT32) code << cur_bits);
  132.   else
  133.     cur_accum = code;
  134.   cur_bits += n_bits;
  135.  
  136.   while (cur_bits >= 8) {
  137.     char_out((char) (cur_accum & 0xFF));
  138.     cur_accum >>= 8;
  139.     cur_bits -= 8;
  140.   }
  141.  
  142.   /*
  143.    * If the next entry is going to be too big for the code size,
  144.    * then increase it, if possible.  We do this here to ensure
  145.    * that it's done in sync with the decoder's codesize increases.
  146.    */
  147.   if (free_code > maxcode) {
  148.     n_bits++;
  149.     if (n_bits == MAX_LZW_BITS)
  150.       maxcode = LZW_TABLE_SIZE;    /* free_code will never exceed this */
  151.     else
  152.       maxcode = MAXCODE(n_bits);
  153.   }
  154. }
  155.  
  156.  
  157. /* The LZW algorithm proper */
  158.  
  159. static code_int waiting_code;    /* symbol not yet output; may be extendable */
  160. static boolean first_byte;    /* if TRUE, waiting_code is not valid */
  161.  
  162.  
  163. LOCAL void
  164. clear_hash (void)
  165. /* Fill the hash table with empty entries */
  166. {
  167.   /* It's sufficient to zero hash_code[] */
  168.   jzero_far((void FAR *) hash_code, HSIZE * SIZEOF(code_int));
  169. }
  170.  
  171.  
  172. LOCAL void
  173. clear_block (void)
  174. /* Reset compressor and issue a Clear code */
  175. {
  176.   clear_hash();            /* delete all the symbols */
  177.   free_code = ClearCode + 2;
  178.   output(ClearCode);        /* inform decoder */
  179.   n_bits = init_bits;        /* reset code size */
  180.   maxcode = MAXCODE(n_bits);
  181. }
  182.  
  183.  
  184. LOCAL void
  185. compress_init (int i_bits)
  186. /* Initialize LZW compressor */
  187. {
  188.   /* init all the static variables */
  189.   n_bits = init_bits = i_bits;
  190.   maxcode = MAXCODE(n_bits);
  191.   ClearCode = ((code_int) 1 << (init_bits - 1));
  192.   EOFCode = ClearCode + 1;
  193.   free_code = ClearCode + 2;
  194.   first_byte = TRUE;        /* no waiting symbol yet */
  195.   /* init output buffering vars */
  196.   bytesinpkt = 0;
  197.   cur_accum = 0;
  198.   cur_bits = 0;
  199.   /* clear hash table */
  200.   clear_hash();
  201.   /* GIF specifies an initial Clear code */
  202.   output(ClearCode);
  203. }
  204.  
  205.  
  206. LOCAL void
  207. compress_byte (int c)
  208. /* Accept and compress one 8-bit byte */
  209. {
  210.   register hash_int i;
  211.   register hash_int disp;
  212.  
  213.   if (first_byte) {        /* need to initialize waiting_code */
  214.     waiting_code = c;
  215.     first_byte = FALSE;
  216.     return;
  217.   }
  218.  
  219.   /* Probe hash table to see if a symbol exists for
  220.    * waiting_code followed by c.
  221.    * If so, replace waiting_code by that symbol and return.
  222.    */
  223.   i = ((hash_int) c << (MAX_LZW_BITS-8)) + waiting_code;
  224.   /* i is less than twice 2**MAX_LZW_BITS, therefore less than twice HSIZE */
  225.   if (i >= HSIZE)
  226.     i -= HSIZE;
  227.   
  228.   if (hash_code[i] != 0) {    /* is first probed slot empty? */
  229.     if (hash_prefix[i] == waiting_code && hash_suffix[i] == (UINT8) c) {
  230.       waiting_code = hash_code[i];
  231.       return;
  232.     }
  233.     if (i == 0)            /* secondary hash (after G. Knott) */
  234.       disp = 1;
  235.     else
  236.       disp = HSIZE - i;
  237.     while (1) {
  238.       i -= disp;
  239.       if (i < 0)
  240.     i += HSIZE;
  241.       if (hash_code[i] == 0)
  242.     break;            /* hit empty slot */
  243.       if (hash_prefix[i] == waiting_code && hash_suffix[i] == (UINT8) c) {
  244.     waiting_code = hash_code[i];
  245.     return;
  246.       }
  247.     }
  248.   }
  249.  
  250.   /* here when hashtable[i] is an empty slot; desired symbol not in table */
  251.   output(waiting_code);
  252.   if (free_code < LZW_TABLE_SIZE) {
  253.     hash_code[i] = free_code++;    /* add symbol to hashtable */
  254.     hash_prefix[i] = waiting_code;
  255.     hash_suffix[i] = (UINT8) c;
  256.   } else
  257.     clear_block();
  258.   waiting_code = c;
  259. }
  260.  
  261.  
  262. LOCAL void
  263. compress_term (void)
  264. /* Clean up at end */
  265. {
  266.   /* Flush out the buffered code */
  267.   if (! first_byte)
  268.     output(waiting_code);
  269.   /* Send an EOF code */
  270.   output(EOFCode);
  271.   /* Flush the bit-packing buffer */
  272.   if (cur_bits > 0) {
  273.     char_out((char) (cur_accum & 0xFF));
  274.   }
  275.   /* Flush the packet buffer */
  276.   flush_packet();
  277. }
  278.  
  279.  
  280. /* GIF header construction */
  281.  
  282.  
  283. LOCAL void
  284. put_word (UINT16 w)
  285. /* Emit a 16-bit word, LSB first */
  286. {
  287.   putc(w & 0xFF, dcinfo->output_file);
  288.   putc((w >> 8) & 0xFF, dcinfo->output_file);
  289. }
  290.  
  291.  
  292. LOCAL void
  293. put_3bytes (int val)
  294. /* Emit 3 copies of same byte value --- handy subr for colormap construction */
  295. {
  296.   putc(val, dcinfo->output_file);
  297.   putc(val, dcinfo->output_file);
  298.   putc(val, dcinfo->output_file);
  299. }
  300.  
  301.  
  302. LOCAL void
  303. emit_header (int num_colors, JSAMPARRAY colormap)
  304. /* Output the GIF file header, including color map */
  305. /* If colormap==NULL, synthesize a gray-scale colormap */
  306. {
  307.   int BitsPerPixel, ColorMapSize, InitCodeSize, FlagByte;
  308.   int i;
  309.  
  310.   if (num_colors > 256)
  311.     ERREXIT(dcinfo->emethods, "GIF can only handle 256 colors");
  312.   /* Compute bits/pixel and related values */
  313.   if (num_colors <= 2)
  314.     BitsPerPixel = 1;
  315.   else if (num_colors <= 4)
  316.     BitsPerPixel = 2;
  317.   else if (num_colors <= 8)
  318.     BitsPerPixel = 3;
  319.   else if (num_colors <= 16)
  320.     BitsPerPixel = 4;
  321.   else if (num_colors <= 32)
  322.     BitsPerPixel = 5;
  323.   else if (num_colors <= 64)
  324.     BitsPerPixel = 6;
  325.   else if (num_colors <= 128)
  326.     BitsPerPixel = 7;
  327.   else
  328.     BitsPerPixel = 8;
  329.   ColorMapSize = 1 << BitsPerPixel;
  330.   if (BitsPerPixel <= 1)
  331.     InitCodeSize = 2;
  332.   else
  333.     InitCodeSize = BitsPerPixel;
  334.   /*
  335.    * Write the GIF header.
  336.    * Note that we generate a plain GIF87 header for maximum compatibility.
  337.    */
  338.   (void) FWRITE(dcinfo->output_file, "GIF87a", 6);
  339.   /* Write the Logical Screen Descriptor */
  340.   put_word((UINT16) dcinfo->image_width);
  341.   put_word((UINT16) dcinfo->image_height);
  342.   FlagByte = 0x80;        /* Yes, there is a global color table */
  343.   FlagByte |= (BitsPerPixel-1) << 4; /* color resolution */
  344.   FlagByte |= (BitsPerPixel-1);    /* size of global color table */
  345.   putc(FlagByte, dcinfo->output_file);
  346.   putc(0, dcinfo->output_file);    /* Background color index */
  347.   putc(0, dcinfo->output_file);    /* Reserved in GIF87 (aspect ratio in GIF89) */
  348.   /* Write the Global Color Map */
  349.   for (i=0; i < ColorMapSize; i++) {
  350.     if (i < num_colors) {
  351.       if (colormap != NULL) {
  352.     if (dcinfo->out_color_space == CS_RGB) {
  353.       /* Normal case: RGB color map */
  354.       putc(GETJSAMPLE(colormap[0][i]), dcinfo->output_file);
  355.       putc(GETJSAMPLE(colormap[1][i]), dcinfo->output_file);
  356.       putc(GETJSAMPLE(colormap[2][i]), dcinfo->output_file);
  357.     } else {
  358.       /* Grayscale "color map": possible if quantizing grayscale image */
  359.       put_3bytes(GETJSAMPLE(colormap[0][i]));
  360.     }
  361.       } else {
  362.     /* Create a gray-scale map of num_colors values, range 0..255 */
  363.     put_3bytes((i * 255 + (num_colors-1)/2) / (num_colors-1));
  364.       }
  365.     } else {
  366.       /* fill out the map to a power of 2 */
  367.       put_3bytes(0);
  368.     }
  369.   }
  370.   /* Write image separator and Image Descriptor */
  371.   putc(',', dcinfo->output_file); /* separator */
  372.   put_word((UINT16) 0);        /* left/top offset */
  373.   put_word((UINT16) 0);
  374.   put_word((UINT16) dcinfo->image_width); /* image size */
  375.   put_word((UINT16) dcinfo->image_height);
  376.   /* flag byte: not interlaced, no local color map */
  377.   putc(0x00, dcinfo->output_file);
  378.   /* Write Initial Code Size byte */
  379.   putc(InitCodeSize, dcinfo->output_file);
  380.  
  381.   /* Initialize for LZW compression of image data */
  382.   compress_init(InitCodeSize+1);
  383. }
  384.  
  385.  
  386.  
  387. /*
  388.  * Initialize for GIF output.
  389.  */
  390.  
  391. METHODDEF void
  392. output_init (decompress_info_ptr cinfo)
  393. {
  394.   dcinfo = cinfo;        /* save for use by local routines */
  395.   if (cinfo->final_out_comps != 1) /* safety check */
  396.     ERREXIT(cinfo->emethods, "GIF output got confused");
  397.   /* Allocate space for hash table */
  398.   hash_code = (code_int FAR *) (*cinfo->emethods->alloc_medium)
  399.                 (HSIZE * SIZEOF(code_int));
  400.   hash_prefix = (code_int FAR *) (*cinfo->emethods->alloc_medium)
  401.                 (HSIZE * SIZEOF(code_int));
  402.   hash_suffix = (UINT8 FAR *) (*cinfo->emethods->alloc_medium)
  403.                 (HSIZE * SIZEOF(UINT8));
  404.   /*
  405.    * If we aren't quantizing, put_color_map won't be called,
  406.    * so emit the header now.  This only happens with gray scale output.
  407.    * (If we are quantizing, wait for the color map to be provided.)
  408.    */
  409.   if (! cinfo->quantize_colors)
  410.     emit_header(256, (JSAMPARRAY) NULL);
  411. }
  412.  
  413.  
  414. /*
  415.  * Write the color map.
  416.  */
  417.  
  418. METHODDEF void
  419. put_color_map (decompress_info_ptr cinfo, int num_colors, JSAMPARRAY colormap)
  420. {
  421.   emit_header(num_colors, colormap);
  422. }
  423.  
  424.  
  425. /*
  426.  * Write some pixel data.
  427.  */
  428.  
  429. METHODDEF void
  430. put_pixel_rows (decompress_info_ptr cinfo, int num_rows,
  431.         JSAMPIMAGE pixel_data)
  432. {
  433.   register JSAMPROW ptr;
  434.   register long col;
  435.   register long width = cinfo->image_width;
  436.   register int row;
  437.   
  438.   for (row = 0; row < num_rows; row++) {
  439.     ptr = pixel_data[0][row];
  440.     for (col = width; col > 0; col--) {
  441.       compress_byte(GETJSAMPLE(*ptr));
  442.       ptr++;
  443.     }
  444.   }
  445. }
  446.  
  447.  
  448. /*
  449.  * Finish up at the end of the file.
  450.  */
  451.  
  452. METHODDEF void
  453. output_term (decompress_info_ptr cinfo)
  454. {
  455.   /* Flush LZW mechanism */
  456.   compress_term();
  457.   /* Write a zero-length data block to end the series */
  458.   putc(0, cinfo->output_file);
  459.   /* Write the GIF terminator mark */
  460.   putc(';', cinfo->output_file);
  461.   /* Make sure we wrote the output file OK */
  462.   fflush(cinfo->output_file);
  463.   if (ferror(cinfo->output_file))
  464.     ERREXIT(cinfo->emethods, "Output file write error");
  465.   /* Free space */
  466.   (*cinfo->emethods->free_medium) ((void FAR *) hash_code);
  467.   (*cinfo->emethods->free_medium) ((void FAR *) hash_prefix);
  468.   (*cinfo->emethods->free_medium) ((void FAR *) hash_suffix);
  469. }
  470.  
  471.  
  472. /*
  473.  * The method selection routine for GIF format output.
  474.  * This should be called from d_ui_method_selection if GIF output is wanted.
  475.  */
  476.  
  477. GLOBAL void
  478. jselwgif (decompress_info_ptr cinfo)
  479. {
  480.   cinfo->methods->output_init = output_init;
  481.   cinfo->methods->put_color_map = put_color_map;
  482.   cinfo->methods->put_pixel_rows = put_pixel_rows;
  483.   cinfo->methods->output_term = output_term;
  484.  
  485.   if (cinfo->out_color_space != CS_GRAYSCALE &&
  486.       cinfo->out_color_space != CS_RGB)
  487.     ERREXIT(cinfo->emethods, "GIF output must be grayscale or RGB");
  488.  
  489.   /* Force quantization if color or if > 8 bits input */
  490.   if (cinfo->out_color_space == CS_RGB || cinfo->data_precision > 8) {
  491.     /* Force quantization to at most 256 colors */
  492.     cinfo->quantize_colors = TRUE;
  493.     if (cinfo->desired_number_of_colors > 256)
  494.       cinfo->desired_number_of_colors = 256;
  495.   }
  496. }
  497.  
  498. #endif /* GIF_SUPPORTED */
  499.